DP S
ある数K以下の自然数で、条件を満たすものがいくつあるか、という問題
素朴にK個の数を調べることはKがやたらでかいのでできない前提
桁DPはもらうDPよりも配るDPの方が圧倒的に書きやすい
なるほど、以前試してバグらせた時はもらう実装でやってた
まずはシンプルに「K以下の自然数の個数を数え上げる」をDPで考える
https://gyazo.com/c9063ac33df020121c1f8d9ce839578a
57以下の自然数の数を数えている
ゼロを含むので「57未満が57個、イコールが1個」となっている
「先頭i桁」を定義域とし、そこまでで「K以下である数」「イコールKである数」の個数を値とするDP
ところで「イコールKである数」は常に1なのだからテーブルで持つ必要はないよね
解説などではテーブルで持ってるものが多くて、その方が複雑な問題だと実装の都合が良いことがあるのかな
今回の問題では追加の条件「Dで割り切れる」のチェックのためにDで割ったあまりごとに数え分けているが、僕の実装では「イコールK」にはテーブルを用意しなかった
code:python
def solve(N, D):
equal = 0
for digit in N:
for new_digit in range(10):
for d in range(D):
if new_digit < digit:
for d in range(D):
less = new_less
equal += digit
equal %= D
ret -= 1 # for x = 0
if equal == 0: # for x = N
ret += 1
return ret % MOD
old version
code:python
def solve(K, D):
N = len(K)
less = [0 * D for i in range(N + 1)] border = 0
for i in range(N):
for j in range(10):
for d in range(D):
border %= D
ret += (border == 0)
return ret % MOD